home *** CD-ROM | disk | FTP | other *** search
/ The CICA Windows Explosion! / The CICA Windows Explosion! - Disc 2.iso / nt / lkbackup.zip / ct_tally.h < prev    next >
C/C++ Source or Header  |  1993-11-03  |  11KB  |  293 lines
  1. #include <ctype.h>
  2.  
  3.  
  4.  /* ===========================================================================
  5.  * Constants */
  6.  
  7.  
  8. #define MAX_BITS 15
  9. /* All codes must not exceed MAX_BITS bits */
  10.  
  11. #define MAX_BL_BITS 7
  12. /* Bit length codes must not exceed MAX_BL_BITS bits */
  13.  
  14. #define LENGTH_CODES 29
  15. /* number of length codes, not counting the special END_BLOCK code */
  16.  
  17. #define LITERALS  256
  18. /* number of literal bytes 0..255 */
  19.  
  20. #define END_BLOCK 256
  21. /* end of block literal code */
  22.  
  23. #define L_CODES (LITERALS+1+LENGTH_CODES)
  24. /* number of Literal or Length codes, including the END_BLOCK code */
  25.  
  26. #define D_CODES   30
  27. /* number of distance codes */
  28.  
  29. #define BL_CODES  19
  30. /* number of codes used to transfer the bit lengths */
  31.  
  32.  
  33. extern int extra_lbits[LENGTH_CODES]; /* extra bits for each length code */
  34.  
  35. extern int extra_dbits[D_CODES]; /* extra bits for each distance code */
  36.  
  37. extern int extra_blbits[BL_CODES];/* extra bits for each bit length code */
  38.  
  39. /* The three kinds of block type */
  40.  
  41. #ifndef LIT_BUFSIZE
  42. #  ifdef SMALL_MEM
  43. #    define LIT_BUFSIZE  0x2000
  44. #  else
  45. #  ifdef MEDIUM_MEM
  46. #    define LIT_BUFSIZE  0x4000
  47. #  else
  48. #    define LIT_BUFSIZE  0x8000
  49. #  endif
  50. #  endif
  51. #endif
  52. #ifndef DIST_BUFSIZE
  53. #  define DIST_BUFSIZE  LIT_BUFSIZE
  54. #endif
  55. /* Sizes of match buffers for literals/lengths and distances.  There are
  56.  * 4 reasons for limiting LIT_BUFSIZE to 64K:
  57.  *   - frequencies can be kept in 16 bit counters
  58.  *   - if compression is not successful for the first block, all input data is
  59.  *     still in the window so we can still emit a stored block even when input
  60.  *     comes from standard input.  (This can also be done for all blocks if
  61.  *     LIT_BUFSIZE is not greater than 32K.)
  62.  *   - if compression is not successful for a file smaller than 64K, we can
  63.  *     even emit a stored file instead of a stored block (saving 5 bytes).
  64.  *   - creating new Huffman trees less frequently may not provide fast
  65.  *     adaptation to changes in the input data statistics. (Take for
  66.  *     example a binary file with poorly compressible code followed by
  67.  *     a highly compressible string table.) Smaller buffer sizes give
  68.  *     fast adaptation but have of course the overhead of transmitting trees
  69.  *     more frequently.
  70.  *   - I can't count above 4
  71.  * The current code is general and allows DIST_BUFSIZE < LIT_BUFSIZE (to save
  72.  * memory at the expense of compression). Some optimizations would be possible
  73.  * if we rely on DIST_BUFSIZE == LIT_BUFSIZE.
  74.  */
  75. #if LIT_BUFSIZE > INBUFSIZ
  76.     error cannot overlay l_buf and inbuf
  77. #endif
  78.  
  79. #define REP_3_6      16
  80. /* repeat previous bit length 3-6 times (2 bits of repeat count) */
  81.  
  82. #define REPZ_3_10    17
  83. /* repeat a zero length 3-10 times  (3 bits of repeat count) */
  84.  
  85. #define REPZ_11_138  18
  86. /* repeat a zero length 11-138 times  (7 bits of repeat count) */
  87.  
  88. /* ===========================================================================
  89.  * Local data
  90.  */
  91.  
  92. /* Data structure describing a single value and its code string. */
  93. typedef struct ct_data {
  94.     union {
  95.         ush  freq;       /* frequency count */
  96.         ush  code;       /* bit string */
  97.     } fc;
  98.     union {
  99.         ush  dad;        /* father node in Huffman tree */
  100.         ush  len;        /* length of bit string */
  101.     } dl;
  102. } ct_data;
  103.  
  104. #define Freq fc.freq
  105. #define Code fc.code
  106. #define Dad  dl.dad
  107. #define Len  dl.len
  108.  
  109. #define HEAP_SIZE (2*L_CODES+1)
  110. /* maximum heap size */
  111.  
  112. extern ct_data dyn_ltree[HEAP_SIZE];   /* literal and length tree */
  113. extern ct_data dyn_dtree[2*D_CODES+1]; /* distance tree */
  114.  
  115. extern ct_data    static_ltree[L_CODES+2];
  116. /* The static literal tree. Since the bit lengths are imposed, there is no
  117.  * need for the L_CODES extra codes used during heap construction. However
  118.  * The codes 286 and 287 are needed to build a canonical tree (see ct_init
  119.  * below).
  120.  */
  121.  
  122. local ct_data    static_dtree[D_CODES];
  123. /* The static distance tree. (Actually a trivial tree since all codes use
  124.  * 5 bits.)
  125.  */
  126.  
  127. local ct_data    bl_tree[2*BL_CODES+1];
  128. /* Huffman tree for the bit lengths */
  129.  
  130. typedef struct tree_desc {
  131.     ct_data    *dyn_tree;      /* the dynamic tree */
  132.     ct_data    *static_tree;   /* corresponding static tree or NULL */
  133.     int        *extra_bits;    /* extra bits for each code or NULL */
  134.     int     extra_base;          /* base index for extra_bits */
  135.     int     elems;               /* max number of elements in the tree */
  136.     int     max_length;          /* max bit length for the codes */
  137.     int     max_code;            /* largest code with non zero frequency */
  138. } tree_desc;
  139.  
  140. extern tree_desc    l_desc;
  141. extern tree_desc    d_desc;
  142. extern tree_desc    bl_desc;
  143.  
  144.  
  145. extern ush    bl_count[MAX_BITS+1];
  146. /* number of codes at each bit length for an optimal tree */
  147.  
  148. extern uch    bl_order[BL_CODES];
  149. /* The lengths of the bit length codes are sent in order of decreasing
  150.  * probability, to avoid transmitting the lengths for unused bit length codes.
  151.  */
  152.  
  153. extern int    heap[2*L_CODES+1]; /* heap used to build the Huffman trees */
  154. extern int heap_len;               /* number of elements in the heap */
  155. extern int heap_max;               /* element of largest frequency */
  156. /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
  157.  * The same heap array is used to build all trees.
  158.  */
  159.  
  160. extern uch    depth[2*L_CODES+1];
  161. /* Depth of each subtree used as tie breaker for trees of equal frequency */
  162.  
  163. extern uch length_code[MAX_MATCH-MIN_MATCH+1];
  164. /* length code for each normalized match length (0 == MIN_MATCH) */
  165.  
  166. extern uch dist_code[512];
  167. /* distance codes. The first 256 values correspond to the distances
  168.  * 3 .. 258, the last 256 values correspond to the top 8 bits of
  169.  * the 15 bit distances.
  170.  */
  171.  
  172. extern int    base_length[LENGTH_CODES];
  173. /* First normalized length for each code (0 = MIN_MATCH) */
  174.  
  175. extern int    base_dist[D_CODES];
  176. /* First normalized distance for each code (0 = distance of 1) */
  177.  
  178. #define l_buf inbuf
  179. /* DECLARE(uch, l_buf, LIT_BUFSIZE);  buffer for literals or lengths */
  180.  
  181. /* DECLARE(ush, d_buf, DIST_BUFSIZE); buffer for distances */
  182.  
  183. extern uch    flag_buf[(LIT_BUFSIZE/8)];
  184. /* flag_buf is a bit array distinguishing literals from lengths in
  185.  * l_buf, thus indicating the presence or absence of a distance.
  186.  */
  187.  
  188. extern unsigned last_lit;    /* running index in l_buf */
  189. extern unsigned last_dist;   /* running index in d_buf */
  190. extern unsigned last_flags;  /* running index in flag_buf */
  191. extern uch flags;            /* current flags not yet saved in flag_buf */
  192. extern uch flag_bit;         /* current bit used in flags */
  193. /* bits are filled in flags starting at bit 0 (least significant).
  194.  * Note: these flags are overkill in the current code since we don't
  195.  * take advantage of DIST_BUFSIZE == LIT_BUFSIZE.
  196.  */
  197.  
  198. extern ulg opt_len;        /* bit length of current block with optimal trees */
  199. extern ulg static_len;     /* bit length of current block with static trees */
  200.  
  201. extern ulg compressed_len; /* total bit length of compressed file */
  202.  
  203. extern ulg input_len;      /* total byte length of input file */
  204. /* input_len is for debugging only since we can get it by other means. */
  205.  
  206. extern ush *file_type;        /* pointer to UNKNOWN, BINARY or ASCII */
  207. extern int *file_method;      /* pointer to DEFLATE or STORE */
  208.  
  209. #ifdef DEBUG
  210. extern ulg bits_sent;  /* bit length of the compressed data */
  211. extern long isize;     /* byte length of input file */
  212. #endif
  213.  
  214. extern long block_start;       /* window offset of current block */
  215. extern unsigned    strstart; /* window offset of current string */
  216.  
  217.  
  218. #ifndef DEBUG
  219. #  define send_code(c, tree) send_bits(tree[c].Code, tree[c].Len)
  220.    /* Send a code of the given tree. c and tree must not have side effects */
  221.  
  222. #else /* DEBUG */
  223. #  define send_code(c, tree) \
  224.      { if (verbose>1) fprintf(stderr,"\ncd %3d ",(c)); \
  225.        send_bits(tree[c].Code, tree[c].Len); }
  226. #endif
  227.  
  228. #define d_code(dist) \
  229.    ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)])
  230. /* Mapping from a distance to a distance code. dist is the distance - 1 and
  231.  * must not have side effects. dist_code[256] and dist_code[257] are never
  232.  * used.
  233.  */
  234.  
  235. #define MAX(a,b) (a >= b ? a : b)
  236. /* the arguments must not have side effects */
  237. /* ===========================================================================
  238.  * Save the match info and tally the frequency counts. Return true if
  239.  * the current block must be flushed.
  240.  */
  241.  /* lgk make this function inline and use registers since it gets called 150K
  242.     times in a little example */
  243.     
  244. _inline int ct_tally (dist, lc)
  245.     register int dist;  /* distance of matched string */
  246.     register int lc;    /* match length-MIN_MATCH or unmatched char (if dist==0) */
  247. {
  248.     l_buf[last_lit++] = (uch)lc;
  249.     if (dist == 0) {
  250.         /* lc is the unmatched char */
  251.         dyn_ltree[lc].Freq++;
  252.     } else {
  253.         /* Here, lc is the match length - MIN_MATCH */
  254.         dist--;             /* dist = match distance - 1 */
  255.         Assert((ush)dist < (ush)MAX_DIST &&
  256.                (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
  257.                (ush)d_code(dist) < (ush)D_CODES,  "ct_tally: bad match");
  258.  
  259.         dyn_ltree[length_code[lc]+LITERALS+1].Freq++;
  260.         dyn_dtree[d_code(dist)].Freq++;
  261.  
  262.         d_buf[last_dist++] = (ush)dist;
  263.         flags |= flag_bit;
  264.     }
  265.     flag_bit <<= 1;
  266.  
  267.     /* Output the flags if they fill a byte: */
  268.     if ((last_lit & 7) == 0) {
  269.         flag_buf[last_flags++] = flags;
  270.         flags = 0, flag_bit = 1;
  271.     }
  272.     /* Try to guess if it is profitable to stop the current block here */
  273.     if (level > 2 && (last_lit & 0xfff) == 0) {
  274.         /* Compute an upper bound for the compressed length */
  275.         register ulg out_length = (ulg)last_lit*8L;
  276.         register ulg in_length = (ulg)strstart-block_start;
  277.         register int dcode;
  278.         for (dcode = 0; dcode < D_CODES; dcode++) {
  279.             out_length += (ulg)dyn_dtree[dcode].Freq*(5L+extra_dbits[dcode]);
  280.         }
  281.         out_length >>= 3;
  282.         Trace((stderr,"\nlast_lit %u, last_dist %u, in %ld, out ~%ld(%ld%%) ",
  283.                last_lit, last_dist, in_length, out_length,
  284.                100L - out_length*100L/in_length));
  285.         if (last_dist < last_lit/2 && out_length < in_length/2) return 1;
  286.     }
  287.     return (last_lit == LIT_BUFSIZE-1 || last_dist == DIST_BUFSIZE);
  288.     /* We avoid equality with LIT_BUFSIZE because of wraparound at 64K
  289.      * on 16 bit machines and because stored blocks are restricted to
  290.      * 64K-1 bytes.
  291.      */
  292. }
  293.